package com.gq.webstore.hdzw;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class TestFind {
    public static void main(String[] args) {
        System.out.println("石桩的位置数组 0是没有石桩  1是石桩完全降下来 2是石桩半升起  3是石桩完全升起");
        int[][] arr = {
                {1, 0, 1, 0},
                {3, 1, 3, 0},
                {1, 0, 1, 0},
        };
        for (int[] ar : arr) {
            System.out.println(Arrays.toString(ar));
        }
        List<Model> list = getList(arr);
        if (list == null || list.isEmpty()) {
            System.out.println("没有石桩");
            return;
        }
        Task t = find(arr, list);
        if (t.minList == null) {
            System.out.println("计算失败,石桩无解法,计算次数:" + t.cnt);
            return;
        }

        System.out.println("计算成功,计算次数:" + t.cnt + ",解法共计:" + t.sucCnt + ",最短路径:" + t.minList.size() + "步,最长路径:" + t.maxList.size() + "步");

        System.out.println("最佳敲打石桩的顺序  x是横坐标 y是纵坐标");
        for (Model m : t.minList) {
            System.out.println(m.x + "," + m.y);
        }
    }

    private static Task find(int[][] orgArr, List<Model> orgList) {
        int[][] arr = copy(orgArr);
        int size = (orgList.size() * 3) + 1;
        LinkedList<Model> steps = new LinkedList<>();
        Task t = new Task();
        t.arr = arr;
        t.orgArr = orgArr;
        t.orgList = orgList;
        t.max = size;
        digui(t, steps);
        return t;
    }

    private static boolean digui(Task t, LinkedList<Model> curList) {
        int[][] arr = t.arr;
        List<Model> orgList = t.orgList;
        int max = t.max;
        if (check(arr)) {
            return true;
        } else if (curList.size() > max) {
            return false;
        } else if (t.minList != null && curList.size() >= t.minList.size()) {
            return false;
        }
        for (Model m : orgList) {
            curList.addLast(m);
            t.cnt.incrementAndGet();
            att(arr, m.x, m.y, true, false);
            boolean over = digui(t, curList);
            if (over) {
                t.sucCnt.incrementAndGet();
                if (t.minList == null || t.minList.size() > curList.size()) {
                    t.minList = new ArrayList<>(curList);
                }
                if (t.maxList == null || t.maxList.size() < curList.size()) {
                    t.maxList = new ArrayList<>(curList);
                }
            }
            boolean same = same(arr, t.orgArr, t.orgList);
            curList.removeLast();
            att(arr, m.x, m.y, false, false);
            if (same) {
                return false;
            }
            if (over) {
                break;
            }
        }
        return false;
    }


    private static boolean digui1(Task t, LinkedList<Model> curList) {
        int[][] arr = t.arr;
        List<Model> orgList = t.orgList;
        int max = t.max;
        if (check(arr)) {
            return true;
        }
        for (Model m : t.orgList) {
            for (int i = 0; i < 3; i++) {

            }
        }
        return false;
    }

    private static boolean same(int[][] arr, int[][] orgArr, List<Model> orgList) {
        for (Model model : orgList) {
            if (arr[model.y][model.x] != orgArr[model.y][model.x]) {
                return false;
            }
        }
        return true;
    }


    private static void att(int[][] arr, int x, int y, boolean type, boolean flag) {
        if (x < 0 || y < 0 || y >= arr.length || x >= arr[y].length) {
            return;
        }
        if (arr[y][x] == 0) {
            return;
        }

        if (type) {
            arr[y][x] += 1;
            if (arr[y][x] > 3) {
                arr[y][x] = 1;
            }
        } else {
            arr[y][x]--;
            if (arr[y][x] < 1) {
                arr[y][x] = 3;
            }
        }
        if (flag) {
            return;
        }
        att(arr, x + 1, y, type, true);
        att(arr, x - 1, y, type, true);
        att(arr, x, y + 1, type, true);
        att(arr, x, y - 1, type, true);
    }

    private static boolean check(int[][] arr) {
        for (int[] ints : arr) {
            for (int anInt : ints) {
                if (anInt != 0 && anInt != 3) {
                    return false;
                }
            }
        }
        return true;
    }

    private static int[][] copy(int[][] arr) {
        if (arr == null) {
            return null;
        }
        int[][] r = new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            r[i] = new int[arr[i].length];
            System.arraycopy(arr[i], 0, r[i], 0, arr[i].length);
        }
        return r;
    }

    private static List<Model> getList(int[][] arr) {
        List<Model> list = new ArrayList<>();

        int cnt = 0;

        for (int y = 0; y < arr.length; y++) {
            for (int x = 0; x < arr[y].length; x++) {
                if (arr[y][x] != 0) {
                    list.add(new Model(x, y));
                }
            }
        }
        return list;
    }


    private static class Task {
        private final AtomicInteger cnt = new AtomicInteger();
        private final AtomicInteger sucCnt = new AtomicInteger();
        private int[][] arr;
        private int[][] orgArr;
        private List<Model> orgList;
        private int max;
        private List<Model> minList;
        private List<Model> maxList;
    }

    private static class Model {
        private int x;
        private int y;
        private int cnt;

        public Model(int x, int y) {
            this(x, y, 1);
        }

        public Model(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}
